/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head){
        if(head==nullptr){
            return nullptr;
        }
        Node* cur=head;
        //先创建map 将 key==cur value==map[cur]放入其中
        unordered_map<Node*,Node*> map;
        while(cur){
            Node* newNode=new Node(cur->val);
            map[cur]=newNode;
            cur=cur->next;
        }
        cur=head;
        //将map中的指向确认清楚
        while(cur){
            Node* valueNode=map[cur];
            //通过原链表的节点确认next的指向
            Node* keynextNode=cur->next;
            //需要value对应的下一个节点
            Node* valuenextNode=map[keynextNode];
            valueNode->next=valuenextNode;
            //通过原链表的指向确认random的指向
            Node* keyrandomNode=cur->random;
            Node* valuerandomNode=map[keyrandomNode];
            valueNode->random=valuerandomNode;

            cur=cur->next;
        }
        return map[head];
    }
};